백준 2156번 - 포도주 시식

문제 링크

풀이과정

현재 포도주를 집을 수 있는지 없는지에 관한 것은 이전 상태에 기반한다
-> 이전 상태를 기록하고 그 상태에 따른 최대값을 memoization해줬다.

포도주 집는 상태를 0,1,2 3개로 구분하여 dp 배열을 세개로 만들어줬다.

코드

import sys

n = int(input())

podo = [int(sys.stdin.readline()) for _ in range(n)]

dp = [[0 for i in range(n + 1)] for j in range(3)]


for i in range(n):
    dp[0][i + 1] = max(dp[1][i], dp[2][i], dp[0][i])
    dp[1][i + 1] = dp[0][i] + podo[i]
    dp[2][i + 1] = dp[1][i] + podo[i]

print(max(dp[0][n], dp[1][n], dp[2][n]))

더 나은 코드

dp 배열 하나로도 풀 수 있다.

현재 상태 대비 마지막까지의 선택을 3가지로 분류하면

1. X
2. XO
3. XOO
   각 이전의 최대값과 해당 podo값을 더한 값 중 큰값을 저장하면 된다.

import sys
input = sys.stdin.readline

def solution():
    n = int(input())
    wine = [int(input()) for _ in range(n)]
    DP = [0]*n
    
    if n == 1:
        print(wine[0])
        return
    
    if n == 2:
        print(wine[0] + wine[1])
        return
    
    if n == 3:
        print(max(wine[0] + wine[1], wine[0] + wine[2], wine[1] + wine[2]))
        return
    
    DP[0] = wine[0]
    DP[1] = wine[0] + wine[1]
    DP[2] = max(wine[0] + wine[1], wine[0] + wine[2], wine[1] + wine[2])
    
    for i in range(3, n):
        DP[i] = max(DP[i-1], wine[i] + wine[i-1] + DP[i-3], wine[i] + DP[i-2])
    
    print(DP[-1])
    return

solution()

관련글

• Dynamic Programming